Mobile ad-hoc networks (MANET's) are becoming increasingly popular because they operate as self-configuring networks of mobile routers or associated hosts connected by wireless links to form an arbitrary topology. The routers, such as wireless mobile units, can move randomly and organize themselves arbitrarily as nodes in a network, similar to a packet radio network. The individual units require a minimum configuration and their quick deployment can make ad-hoc networks suitable for emergency situations. For example, many MANET's are designed for military systems such as the JTRS (Joint Tactical Radio System) and other similar peer-to-peer or Independent Basic Service Set Systems (IBSS).
TDMA technology is becoming more popular for use in these mobile ad-hoc networks. In a TDMA ad-hoc network, channel access scheduling is a core platform of the network structure. Some problems, however, are encountered with distributed channel scheduling used in a multi-hop broadcast networks. As known to those skilled in the art, the optimum channel scheduling problem is equivalent to the graph coloring problem, which is a well known NP-complete problem, cited in numerous sources. Many prior art systems assume that the network topology is known and is not topology transparent.
There is a changing topology in a TDMA ad-hoc network. Before the network is formed, the topology cannot be learned. Without knowing the network topology, the nodes in the network should still find a way to communicate. Once the nodes learn about the transmit and receive schedules among neighboring nodes, these neighboring nodes may have moved away, disappeared, or new nodes may have moved in. The rate of resolving the scheduling must be fast and bandwidth efficient such that the network can be stabilized.
Nodes operative in a TDMA MANET typically use a crystal as part of its clock. Each node's clock should be synchronized, but typically there is some deviation such that each node (or radio) could have a different clock timing. This can occur even when higher quality crystals are used.
As a result, there can be a high network timing dispersion that requires a long guard time. As a result, the time spent for a node to separate from the group of other nodes is limited by how fast its clock drifts from the other clocks in the group. For example, physical radios could have a different clock drift rate, which may also change with temperature. Currently, some first order time tracking occurs where a new timing reference is tracked by an average of time frames of neighboring nodes. Smoothing brings the network timing dispersion down, but its dispersion process does not stop. The time span for a node to leave the group without synchronization problems, however, is still limited by the divergence of the clock drift. A long guard time is still required.
It is possible for an internal clock of a node to adjust periodically to a GPS time such that any network timing dispersion is minimized. GPS must be equipped at each node, however, and a GPS signal is not always available. Some proposals have a time server distribute a time stamp as a standard network clock, and all nodes resynchronize their internal clock to the new time stamp. The network timing dispersion resulting from clock draft, however, continues and a long guard time is required.